#include<bits/stdc++.h>
using namespace std;
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

const double EPS=1e-10;

int F[(1<<19)]; 
struct node{
	double x,y;
}poi[20]; 
int n,m; 
int Map[20][20];
double a,b;

void init()
{
	memset(F,0x3f3f3f3f,sizeof(F));
	memset(Map,0,sizeof(Map));
	a=b=0.0;
	return ;
}

int main()
{
	freopen("angrybirds.in","r",stdin);
	freopen("angrybirds.out","w",stdout);
	int t;
	read(t);
	while(t--)
	{
		init();
		read(n);read(m);
		for(int i=1;i<=n;++i)scanf("%lf%lf",&poi[i].x,&poi[i].y);
		for(int i=1;i<=n;++i)
		{
			for(int j=i+1;j<=n;++j)
			{
				a=(poi[j].y-(poi[i].y*poi[j].x)/poi[i].x)/(poi[j].x*poi[j].x-poi[i].x*poi[j].x);
				b=(poi[j].y-poi[j].x*poi[j].x*a)/poi[j].x;
				if(a>=0)continue;
				for(int k=1;k<=n;++k)
				{
					if(abs(poi[k].x*poi[k].x*a+poi[k].x*b-poi[k].y)<=EPS)Map[i][j]+=(1<<(k-1));
				}
			}
		}
		F[0]=0;
		int p=(1<<n)-1;
		for(int i=0;i<p;++i)
		{
			if(F[i]>n+1)continue;
			for(int x=1;x<=n;++x)
			{
				if(!(i&(1<<(x-1))))
				{
					F[i+(1<<(x-1))]=min(F[i+(1<<(x-1))],F[i]+1);
					for(int y=x+1;y<=n;++y)
					{
						if(!(i&(1<<(y-1))))
						{
							int z=(i|Map[x][y]);
							F[z]=min(F[z],F[i]+1);
						}
					}
				}
			}
		}
		printf("%d\n",F[p]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
